package 链表;

import java.util.*;

/*
 * https://leetcode-cn.com/problems/valid-parentheses/
 * */
public class _20_有效的括号 {
	public boolean isValid(String s) {
		int len = s.length();
		Stack<Character> leftStack = new Stack<Character>();
		for (int i = 0; i < len; i++) {
			char c = s.charAt(i);
			if (c == '(' || c == '{' || c == '[') {
				if (i == len - 1) {
					return false;
				}
				leftStack.push(c);

			} else {
				if (leftStack.isEmpty()) {
					return false;
				}
				char leftTop = leftStack.peek();

				if ((leftTop == '(' && c == ')') || (leftTop == '{' && c == '}') || (leftTop == '[' && c == ']')) {
					leftStack.pop();
				} else {
					return false;
				}
			}
		}
		if (!leftStack.isEmpty()) {
			return false;
		}
		return true;
	}
}
